#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == nullptr)
            return nullptr;
        if (root->val < low)
            return trimBST(root->right, low, high);
        if (root->val > high)
            return trimBST(root->left, low, high);
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;
    }
};

class Solution {
public:
    TreeNode* _sortedArrayToBSTR(vector<int>& nums, int left, int right)
    {
        if (left > right)
            return nullptr;
        int mid = left + ((right - left) >> 1);
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = _sortedArrayToBSTR(nums, left, mid - 1);
        root->right = _sortedArrayToBSTR(nums, mid + 1, right);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return _sortedArrayToBSTR(nums, 0, nums.size() - 1);
    }
};

class Solution {
public:
    TreeNode* _convertBSTR(TreeNode* root, int& num)
    {
        if (root == nullptr)
            return nullptr;
        _convertBSTR(root->right, num);
        num += root->val;
        root->val = num;
        _convertBSTR(root->left, num);
        return root;
    }
    TreeNode* convertBST(TreeNode* root) {
        int num = 0;
        return _convertBSTR(root, num);
    }
};